A communication or computing network is composed of several or many devices that are physically connected through a communication medium, for example a metal or fiber optic cable. One type of device that can be included in a network is a concentrator. For example, a large-scale time-division switching network may include a central switching network and a series of concentrators that are connected to input and output terminals of other devices in the switching network.
Concentrators are typically used to support multiport connectivity to a network. A concentrator is a device that is connected to a plurality of shared communications lines that concentrates information onto fewer lines. Concentrators inherently reduce the capacity of an interconnect path by increasing the occurrence of blocking and data loss, or by calling for storage of information in buffers.
A persistent problem that arises in massively parallel computing and in communications occurs when moving the data to the processors and users. This problem is exacerbated in systems that incorporate concentrators due to the inherent reduction in capacity.
What is needed is a concentrator structure that rapidly routes data and improves information flow by avoiding blockages, that is scaleable virtually without limit, and that supports low latency and high throughput.
An interconnect structure substantially improves operation of an information concentrator through usage of single-bit routing through control cells using a control signal. The terms xe2x80x9ccellxe2x80x9d or xe2x80x9ccontrol cellxe2x80x9d refer to a simple switching element. The term xe2x80x9cnodexe2x80x9d refers to a cell or group of cells that operate as a unit. The interconnect structure and operating technique support wormhole routing and flow of messages. Message packets entering the structure are never discarded, so that any packet that enters the structure is guaranteed to exit.
In accordance with an aspect of the present invention, an interconnect structure includes a ribbon of interconnect lines connecting a plurality of nodes in nonintersecting paths. The ribbon of interconnect lines winds through a plurality of levels from the source level to the destination level. The number of turns of a winding decreases from the source level to the destination level. The interconnect structure further includes a plurality of columns formed by interconnect lines coupling the nodes across the ribbon in cross-section through the windings of the levels. A method of communicating data over the interconnect structure incorporates a high-speed minimum logic method for routing data packets down multiple hierarchical levels.